#include "lcs.h"
#include <cstring>
#include <iostream>

using namespace std;
enum direction{k_init,k_left,k_up,k_left_up};


void lcs_print(int **lcs_direction,char* pstr1,char* pstr2,size_t col,size_t row){
	if(pstr1 == NULL || pstr2 == NULL)
		return ;
	size_t str1_len = strlen(pstr1);
	size_t str2_len = strlen(pstr2);
	if (str1_len == 0 || str2_len == 0 ||!(row < str1_len && col < str2_len))
		return;

	if (lcs_direction[row][col] == k_left_up){
		if (row > 0 && col > 0)
			lcs_print(lcs_direction,pstr1,pstr2,col-1,row-1);
			cout<<pstr1[row];
	} else if (lcs_direction[row][col] == k_left){
		if (col > 0)
			lcs_print(lcs_direction,pstr1,pstr2,col-1,row);
	}
	else if (lcs_direction[row][col] == k_up){
		if (row > 0)
			lcs_print(lcs_direction,pstr1,pstr2,col,row-1);
	}
}


void lcs(char* pstr1,char* pstr2){
	if(pstr1 == NULL || pstr2 == NULL)
		return ;
	size_t str1_len = strlen(pstr1);
	size_t str2_len = strlen(pstr2);
	if (str1_len == 0 || str2_len == 0)
		return;

	int **lcs_len ;
	int **lcs_direction; 
	lcs_len = new int*[str1_len]; 
	lcs_direction = new int*[str1_len]; 
	for (int i = 0; i < str1_len; ++i){
		lcs_len[i] = new int[str2_len];
		lcs_direction[i] = new int[str2_len];
	}
	for (int i = 0; i < str1_len; ++i)
		for (int j = 0; j < str2_len; ++j){
			lcs_len[i][j] = 0;
			lcs_direction[i][j] = k_init;
		}
	for (int i = 0; i < str1_len; ++i)
		for (int j = 0; j < str2_len; ++j){
			if (i == 0 || j == 0){
				if (pstr1[i] == pstr2[j]){
					lcs_len[i][j] = 1;
					lcs_direction[i][j] = k_left_up;
				}
				else {
					if (i > 0){
						lcs_len[i][j] = lcs_len[i-1][j];
						lcs_direction[i][j] = k_up;
					}
					if (j > 0){
						lcs_len[i][j] = lcs_len[i][j-1];
						lcs_direction[i][j] = k_left;
					}
				}
			}
			else {
				if (pstr1[i] == pstr2[j]){
					lcs_len[i][j] = lcs_len[i-1][j-1] + 1;
					lcs_direction[i][j] = k_left_up;
				}
				else if (lcs_len[i-1][j] > lcs_len[i][j-1]){
					lcs_len[i][j] = lcs_len[i-1][j];
					lcs_direction[i][j] = k_up;
				}
				else {
					lcs_len[i][j] = lcs_len[i][j-1];
					lcs_direction[i][j] = k_left;
				}
			}
		}
	lcs_print(lcs_direction,pstr1,pstr2,str2_len-1,str1_len-1);
}

